Một Hệ thống kiểm chứng ngẫu nhiên với tham số toàn vẹn c(n), tham số đúng đắn s(n), bảng chữ cái Σ, cho bài toán quyết định L, với 0 ≤ s ( n ) < c ( n ) ≤ 1 {\displaystyle 0\leq s(n)<c(n)\leq 1} là một máy Turing ngẫu nhiên sử dụng máy tiên tri, tạm gọi là V, sao cho với dữ liệu vào x, và chứng minh π ∈ Σ ∗ {\displaystyle \pi \in \Sigma ^{*}} đọc thông qua máy tiên tri,

• Điều kiện toàn vẹn: Nếu x ∈ L {\displaystyle x\in L} thì tồn tại π sao cho V π ( x ) = 1 {\displaystyle V^{\pi }(x)=1} với xác suất ít nhất c(n).
• Điều kiện đúng đắn: Nếu x ∉ L {\displaystyle x\not \in L} thì với mọi π’, V π ( x ) = 1 {\displaystyle V^{\pi }(x)=1} với xác suất tối đa s(n).

Hai tham số quan trọng khác của hệ thống là số lượng tối đa bit ngẫu nhiên r(n) và số lượng tối đa bit của chứng minh q(n) mà máy V sử dụng khi xử lý dữ liệu vào có độ dài n.

Hệ thống kiểm chứng là không thích ứng nếu V đưa ra vị trí tất cả các bit cần đọc từ chứng minh trước khi nhận được bất kì một bit nào.